package com.jxb.five;

/**
 * 搜索旋转排序数组
 * 示例 1：
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 * 示例2：
 * 输入：nums = [4,5,6,7,0,1,2], target = 3
 * 输出：-1
 * 示例 3：
 * 输入：nums = [1], target = 0
 * 输出：-1
 *
 * 思路：基于二分查找法进行查找
 *  1：当nums[mid]>nums[0] && target > nums[0],将mid右侧的数据变成正无穷大
 *  2：当nums[mid]>nums[0] && target < nums[0],将mid左侧的数据变成负无穷大
 */
public class SearchRotatedSortedArray_33 {

    public static void main(String[] args) {
        int[] nums = {1,3};
        System.out.println(search(nums, 3));
    }


    public static int search(int[] nums, int target) {
        int min = Integer.MIN_VALUE;
        int max = Integer.MAX_VALUE;
        int midIndex = nums.length/2;
        //获取中间元素
        int mid = nums[midIndex];
        //判断是左无穷大还是右无穷大
        //右侧正无穷大
        if (mid > nums[0] && target > nums[0]) {
            //将中间元素后面的位置设置为正无穷大
            int index = midIndex;
            while (index < nums.length) {
                nums[index] = max;
                index++;
            }
        }else if (mid > nums[0] && target < nums[0]) {
            int index = midIndex;
            while (index >=0 ) {
                nums[index] = min;
                index--;
            }
        }else if (target == mid){
            return midIndex;
        }
        //进行二分查找
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int midE = (end + start)/2;
            if (target > nums[midE]) {
                start = midE + 1;
            }else if (target < nums[midE]) {
                end = midE - 1;
            }else {
                return midE;
            }
        }
        return -1;
    }

    public static int search1(int[] nums, int target) {
        int start = 0,end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end)/2;
            int numMid = nums[mid];
            if (numMid == target) {
                return mid;
            }
            //让每一次的择半查找的元素都有序
            //当前元素是有序的：numMid < nums[0] && target < nums[0] 或者 numMid > nums[0] && target > nums[0]
            //负责不是有序的，需要通过负无穷大和正无穷大来替换中间元素，保证元素有序
                //当中间元素大于起始元素，将中间元素设置为正无穷大
                //当中间元素小于起始元素，将中间元素设置为负无穷大
            if (!((numMid < nums[0]) == (target < nums[0]))) {
                numMid = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            if (numMid < target) {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }

    //基于数组一半有序的原理
    public static int search2(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end)/2;
            int num = nums[mid];
            if (target == num) {
                return mid;
            }
            //左半段有序
            //eg:1245670
            if (nums[start] <= num) {
                //判断target是否在左半段中
                if (target >= nums[start] && target <num) {
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
                //右半段有序
            }else {
                if (target > num && target <= nums[end]) {
                    start = mid + 1;
                }else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }


}
